#include <stdio.h>
#include <string.h>
#include "Stack.h"
#include "MergeSort.h"

void MergeSort::Merge(int list[], int sort[], int i, int m, int n)
{
	int k = i;
	int j = m + 1;
	while(i<=m && j<=n) {
		if (list[i] <= list[j]) sort[k++] = list[i++];
		else sort[k++] = list[j++];			
	}		
	
	if (i > m) {		
		for(int t = j; t<=n; ++t) {
			sort[k+t-j] = list[t];
		}	
	} else {
		for(int t = i; t<=m; ++t) {
			sort[k+t-i] = list[t];
		}	
	}	
}

void MergeSort::MergePass(int list[], int sort[], int n, int length)
{
	int i, j;
	for(i=0; i<=n-2*length; i+=2*length) {
		Merge(list, sort, i, i+length-1, i+2*length-1);	
	}		

	if (i + length < n) {
		Merge(list, sort, i, i+length-1, n-1);	
	} else {
		for(j=i; j<n; ++j) {
			sort[j] = list[j];
		}	
	}
}

void MergeSort::Iterative(int list[], int n)
{
	int length = 1;
	int *sort = new int[n];
	while(length < n) {
		MergePass(list, sort, n, length);
		length *= 2;
		MergePass(sort, list, n, length);
		length *= 2;	
	}	
	delete []sort;
}

void MergeSort::Iterative2(int list[], int n)
{
	int *sort = new int[n];

	Stack c;
	int left = 0, right = n - 1;
	c.Push(left, right);
	while(c.size() > 0) {
		c.Top(left, right);
		c.pop();

		if (left < right) {
			int mid = (left+right)/2;
			c.Push(left, mid);
			c.Push(mid+1, right);					
	
			Merge(list, sort, left, mid, right);
			for(int i=left; i<=right; ++i) {
				list[i] = sort[i];
			}	
		}				
	}			

	delete []sort;
}

void MergeSort::Recursive(int list[], int sort[], int left, int right)
{
	if (left < right) {
		int mid = (left+right)/2;
		Recursive(list, sort, left, mid);
		Recursive(list, sort, mid+1, right);
		Merge(list, sort, left, mid, right);									
			
		for(int i=left; i<=right; ++i) {
			list[i] = sort[i];
		}	
	}				
}

void MergeSort::Recursive(int list[], int n)
{
	int *sort = new int[n];
	Recursive(list, sort, 0, n-1);
	delete []sort;
}
